package leetcode.day_2021_3_1_2022_3_7;

/**
 * 43. 字符串相乘
 * https://leetcode-cn.com/problems/multiply-strings/
 */
public class LeetCode0043 {

    public static String multiply(String num1, String num2) {
        StringBuilder str1 = new StringBuilder();
        StringBuilder o = new StringBuilder();
        int alength = num1.length()-1;
        int blength = num2.length()-1;
        int num = 0;
        for (int i=blength; i>=0; i--) {
            StringBuilder str2 = new StringBuilder();
            num = 0; // 保存进数
            for (int j=alength; j>=0; j--) {
                int a = num2.charAt(i) - '0';
                int b = num1.charAt(j) - '0';
                int res = a * b + num;
                num = 0;
                if (res/10 != 0) {
                    num = res/10;
                    res = res%10;
                }
                str2.append(res);
            }
            str1 = strPlus(str1, str2.reverse().append(o));
            o.append("0");

        }
        if (num != 0) str1.append(num).reverse();
        return str1.toString();
    }

    /**
     *
     * @param s1
     * @param s2
     * @return
     */
    public static StringBuilder strPlus(StringBuilder s1, StringBuilder s2) {
        int s1Len = s1.length();
        int s2Len = s2.length();
        if (s1Len == 0) return s2;
        StringBuilder res = new StringBuilder();
        int count = s2Len - s1Len;
        StringBuilder s1demo = s1.reverse();
        for (int i=0; i<count; i++) {
            s1demo.append("0");
        }
        s1 = s1demo.reverse();
        int num = 0;
        for (int i=s2Len-1; i>=0; i--) {
            int a = s1.charAt(i) - '0';
            int b = s2.charAt(i) - '0';
            int sum = a + b + num;
            num = 0;
            if (sum / 10 != 0) {
                num = sum/10;
                sum = sum % 10;
            }
            res.append(sum);
        }
        return res.reverse();
    }

    public static void main(String[] args) {
        System.out.println(multiply("9", "9"));
    }
}
